package gold.digger;

import gold.utils.InputUtil;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LCJZOF094 {
    public long startExecuteTime = System.currentTimeMillis();


    /**
     * 状态定义：dp[i]的含义为字符串长度从0到i,最少可以分为几个回文串
     * 状态转移方程：当前字符串长度为[0,i]时，如果存在0<j<i && [j,i]是回文串的话，那么dp[i]=Math.min(dp[i],dp[j]+1);
     */
    class Solution {
        public int minCut(String s) {
            int n = s.length();
            int[] dp = new int[n + 1];
            dp[0] = 0;
            for (int i = 1; i <= n; i++) {
                dp[i] = i;
                for (int j = 0; j < i; j++) {
                    if (valid(s, j, i - 1)) {
                        dp[i] = Math.min(dp[i], dp[j] + 1);
                    }
                }
            }
            return dp[n] - 1;
        }

        public boolean valid(String s, int l, int r) {
            while (l < r) {
                if (s.charAt(l) != s.charAt(r)) {
                    return false;
                }
                l++;
                r--;
            }
            return true;
        }
    }

    class Solution_Complex_Thought {
        public int minCut(String s) {
            int len = s.length();
            int[][] dp = new int[len][len];

            for (int i = len - 1; i >= 0; i--) {
                for (int j = i; j < len; j++) {
                    if (i == j) dp[i][j] = 0;
                    else if (i + 1 == j) dp[i][j] = s.charAt(i) == s.charAt(j) ? 0 : 1;
                    else {
                        if (curPartIsPalindrome(s, i, j)) {
                            dp[i][j] = 0;
                            continue;
                        }

                        dp[i][j] = Integer.MAX_VALUE;
                        // split i~k, k+1~j
                        for (int k = i; k < j; k++) {
                            dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + 1);
                        }
                    }
                }
            }

            return dp[0][len - 1];
        }

        public boolean curPartIsPalindrome(String s, int i, int j) {
            while (i <= j) {
                if (s.charAt(i++) != s.charAt(j--)) return false;
            }

            return true;
        }
    }

    public void run() {
        System.out.println(new Solution().minCut("aab"));
        System.out.println(new Solution().minCut("a"));
        System.out.println(new Solution().minCut("an"));
        System.out.println(new Solution().minCut("aaba"));
        System.out.println(new Solution().minCut("fiefhgdcdcgfeibggchibffahiededbbegegdfibdbfdadfbdbceaadeceeefiheibahgececggaehbdcgebaigfacifhdbecbebfhiefchaaheiichgdbheacfbhfiaffaecicbegdgeiaiccghggdfggbebdaefcagihbdhhigdgbghbahhhdagbdaefeccfiaifffcfehfcdiiieibadcedibbedgfegibefagfccahfcbegdfdhhdgfhgbchiaieehdgdabhidhfeecgfiibediiafacagigbhchcdhbaigdcedggehhgdhedaebchcafcdehcffdiagcafcgiidhdhedgaaegdchibhdaegdfdaiiidcihifbfidechicighbcbgibadbabieaafgeagfhebfaheaeeibagdfhadifafghbfihehgcgggffgbfccgafigieadfehieafaehaggeeaaaehggffccddchibegfhdfafhadgeieggiigacbfgcagigbhbhefcadafhafdiegahbhccidbeeagcgebehheebfaechceefdiafgeddhdfcadfdafbhiifigcbddahbabbeedidhaieagheihhgffbfbiacgdaifbedaegbhigghfeiahcdieghhdabdggfcgbafgibiifdeefcbegcfcdihaeacihgdchihdadifeifdgecbchgdgdcifedacfddhhbcagaicbebbiadgbddcbagbafeadhddaeebdgdebafabghcabdhdgieiahggddigefddccfccibifgbfcdccghgceigdfdbghdihechfabhbacifgbiiiihcgifhdbhfcaiefhccibebcahidachfabicbdabibiachahggffiibbgchbidfbbhfcicfafgcagaaadbacddfiigdiiffhbbehaaacidggfbhgeaghigihggfcdcidbfccahhgaffiibbhidhdacacdfebedbiacaidaachegffaiiegeabfdgdcgdacfcfhdcbfiaaifgfaciacfghagceaaebhhibbieehhcbiggabefbeigcbhbcidbfhfcgdddgdffghidbbbfbdhcgabaagddcebaechbbiegeiggbabdhgghciheabdibefdfghbfbfebidhicdhbeghebeddgfdfhefebiiebdchifbcbahaddhbfafbbcebiigadhgcfbebgbebhfddgdeehhgdegaeedfadegfeihcgeefbbagbbacbgggciehdhiggcgaaicceeaefgcehfhfdciaghcbbgdihbhecfbgffefhgiefgeiggcebgaacefidghdfdhiabgibchdicdehahbibeddegfciaeaffgbefbbeihbafbagagedgbdadfdggfeaebaidchgdbcifhahgfdcehbahhdggcdggceiabhhafghegfdiegbcadgaecdcdddfhicabdfhbdiiceiegiedecdifhbhhfhgdbhibbdgafhgdcheefdhifgddchadbdggiidhbhegbdfdidhhfbehibiaacdfbiagcbheabaaebfeaeafbgigiefeaeheabifgcfibiddadicheahgbfhbhddaheghddceedigddhchecaghdegigbegcbfgbggdgbbigegffhcfcbbebdchffhddbfhhfgegggibhafiebcfgeaeehgdgbccbfghagfdbdfcbcigbigaccecfehcffahiafgabfcaefbghccieehhhiighcfeabffggfchfdgcfhadgidabdceediefdccceidcfbfiiaidechhbhdccccaigeegcaicabbifigcghcefaafaefd"));
    }

    public static void main(String[] args) throws Exception {
        LCJZOF094 an = new LCJZOF094();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
